# -*- coding: utf-8 -*-

class MaxPriorityQuene(object):
    """docstring for MaxPriorityQuene"""
    def __init__(self, nums):
        super(MaxPriorityQuene, self).__init__();
        self.nums = nums;
        self.size = len(self.nums);

        # 建立最大堆
        for i in range(self.size // 2 - 1, -1, -1):
            self.max_heapify(i);

    def __str__(self):
        rtn = "["
        for i in range(self.size):
            rtn += str(self.nums[i]) + ", ";
        rtn = rtn[0:-2] + "]";
        return rtn;

    # 维持最大堆特性
    def max_heapify(self, index):
        l = 2 * index + 1;
        r = l + 1;
        largest = index;

        if l < self.size and self.nums[l] > self.nums[largest]:
            largest = l;

        if r < self.size and self.nums[r] > self.nums[largest]:
            largest = r;

        if largest == index:
            return;

        self.nums[largest], self.nums[index] = self.nums[index], self.nums[largest];

        self.max_heapify(largest);

    # 插入一个新元素
    def insert(self, num):
        if self.size == len(self.nums):
            self.nums.append(0);
        self.nums[self.size] = float("-inf");
        self.size += 1;

        self.increase_key(self.size - 1, num);

    # 返回最大值
    def max(self):
        if self.size < 1:
            return None;
        return self.nums[0];

    # 弹出最大值
    def extract_max(self):
        if self.size < 1:
            return None;

        rtn = self.nums[0];

        self.nums[0] = self.nums[self.size - 1];
        self.size -= 1;

        self.max_heapify(0);
        return rtn;

    def increase_key(self, index, value):
        if index > self.size - 1:
            return None;
        if self.nums[index] > value:
            return None;

        self.nums[index] = value;
        parent = index // 2;
        while index > 0 and self.nums[index] > self.nums[parent]:
            self.nums[index], self.nums[parent] = self.nums[parent], self.nums[index];
            index = parent;
            parent = index // 2;


quene = MaxPriorityQuene([1,56,985,12,53,154,32]);
print quene;

# 插入操作
quene.insert(151);
print quene;

# 增大
quene.increase_key(5, 110);
print quene;

# 获取最大值
print quene.max();

# 以次弹出最大值
while quene.max():
    print quene.extract_max();